//BF算法只是简单粗暴地对两个字符串的所有字符依次比较，而RK算法比较的是两个字符串的哈希值。

//用过哈希表的朋友都知道，每一个字符串都可以通过某种哈希算法，转换成一个整型数，这个整型数就是hashcode：
//hashcode = hash（string）
//显然，相对于逐个字符比较两个字符串，仅比较两个字符串的hashcode要容易得多。”


function rabinKarp(str, pattern) {
    //主串长度
    let m = str.length;
    //模式串的长度
    let n = pattern.length;
    //计算模式串的hash值
    let patternCode = hash(pattern);
    //计算主串当中第一个和模式串等长的子串hash值
    let strCode = hash(str.substring(0, n));
    //用模式串的hash值和主串的局部hash值比较。
    //如果匹配，则进行精确比较；如果不匹配，计算主串中相邻子串的hash值。
    for (let i = 0; i < (m - n + 1); i++) {
        if ((strCode == patternCode) && compareString(i, str, pattern)) {
            return i;
        }
        //如果不是最后一轮，更新主串从i到i+n的hash值
        if (i < (m - n)) {
            strCode = nextHash(str, strCode, i, n);
        }
    }
    return -1;
}

function hash(s) {
    //这里采用最简单的hashcode计算方式：
    //把a当做1，把b当中2，把c当中3.....然后按位相加
    let sum = 0;
    for (let i = 0; i < s.length; i++) {
        const charCode = s.charCodeAt(i) - 'a'.charCodeAt(0) + 1;
        console.log('charCode',charCode,s.charAt(i))
        // 检查字符是否在a-z范围内，防止非法输入导致错误结果
        if (charCode >= 1 && charCode <= 26) {
           sum += charCode;
        } else {
           throw new Error('Invalid input, only lowercase letters from a to z are allowed.');
        }
    }

    return sum;
}

function nextHash( str, hash, index,  n) {
    hash -= (str.charCodeAt(index) - 'a'.charCodeAt(0));
    hash += (str.charCodeAt(index + n) - 'a'.charCodeAt(0));
    return hash;
}

function compareString(i,  str, pattern) {
    let strSub = str.substring(i, i + pattern.length);
    return strSub===pattern;
}




let str = "aacdesadsdfer";
let pattern = "adsd";
console.log("第一次出现的位置:" + rabinKarp(str, pattern));